package org.example.algorithm.dichotomy;

import java.util.Arrays;

//示例 1：
//输入：nums = [5,7,7,8,8,10], target = 8
//输出：[3,4]
public class SearchRangeSolution {

    public static void main(String[] args) {
        int[] nums = {5,7,7,8,8,10};
        int target = 8;
        //int[] nums = {3, 3, 3};
        //int target = 3;
        SearchRangeSolution solution = new SearchRangeSolution();
        int[] res = solution.searchRange(nums, target);
        for (int i=0;i<res.length;i++) {
            System.out.println(res[i]);
        }
    }

    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[2];
        Arrays.fill(ans, -1);
        if (nums.length == 0) {
            return ans;
        }
        int len = nums.length;
        int left = 0;
        int right = len-1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] > target) {
                right = middle-1;
            } else if(nums[middle] < target) {
                left = middle+1;
            } else {
                ans[0] = middle;
                right = middle-1;
            }
        }
        if (ans[0] == -1) {
            ans[1] = -1;
            return ans;
        }
        left = ans[0];
        right = len-1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] > target) {
                right = middle - 1;
            } else if(nums[middle] < target) {
                left = middle + 1;
            } else {
                ans[1] = middle;
                left = middle + 1;
            }
        }
        return ans;
    }

    public int[] searchRange2(int[] nums, int target) {
        int[] ans = new int[2];
        Arrays.fill(ans, -1);
        if (nums.length == 0) {
            return ans;
        }
        int left = 0;
        int right = nums.length-1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (target < nums[middle]) {
                right = middle - 1;
            } else if(target > nums[middle]) {
                left = middle + 1;
            } else {
                ans[0] = findLeft(nums, middle, target);
                ans[1] = findRight(nums, middle, target);
                return ans;
            }
        }
        return ans;
    }

    private int findLeft(int[] nums, int end, int target) {
        if (end == 0 || nums[end-1] != target) {
            return end;
        }
        int left = 0;
        int right = end-1;
        int middle = -1;
        while (left<=right) {
            middle = (left+right) /2;
            if (nums[middle] < target) {
                left = middle + 1;
            } else if (nums[middle] == target) {
                if (middle == 0 || nums[middle-1] != target) {
                    return middle;
                } else {
                    right = middle-1;
                }
            }
        }
        return middle;
    }

    private int findRight(int[] nums, int start, int target) {
        if (start == nums.length-1 || nums[start+1] != target) {
            return start;
        }
        int left = start+1;
        int right = nums.length-1;
        int middle = -1;
        while (left<=right) {
            middle = (left + right) / 2;
            if (nums[middle] > target) {
                right = middle-1;
            } else if (nums[middle] == target) {
                if (middle == nums.length-1 || nums[middle+1] != target) {
                    return middle;
                } else {
                    left = middle+1;
                }
            }
        }
        return middle;
    }
}
